package main.java.indi.zyj.hot100;

import java.util.PriorityQueue;
import java.util.Queue;

class MedianFinder {
        PriorityQueue<Integer> queMax;
        PriorityQueue<Integer> queMin;

        public MedianFinder() {
                // 大根堆（保存较小的堆）
                queMax = new PriorityQueue<Integer>((a, b) -> (b - a));
                // 小根堆（保存较大的堆）
                queMin = new PriorityQueue<Integer>((a, b) -> (a - b));
        }

        public void addNum(int num) {
                if (queMax.isEmpty() || num <= queMax.peek()) {
                        queMax.offer(num);
                        if (queMin.size() + 1 < queMax.size()) {
                                queMin.offer(queMax.poll());
                        }
                } else {
                        queMin.offer(num);
                        // 默认大根堆比小根堆多一个
                        if (queMin.size() > queMax.size()) {
                                queMax.offer(queMin.poll());
                        }
                }
        }

        public double findMedian() {
                if (queMax.size() > queMin.size()) {
                        return queMax.peek();
                }
                return (queMax.peek() + queMin.peek()) / 2.0;
        }
}
